#pragma once

#include <iostream>
using namespace std;

template <class K>
struct BSTreeNode
{
    BSTreeNode<K> *_left;
    BSTreeNode<K> *_right;
    K _key;

    BSTreeNode(const K &key)
        : _left(nullptr), _right(nullptr), _key(key)
    {
    }
};

template <class K>
class BSTree
{
public:
    using Node = BSTreeNode<K>;

    BSTree() = default;

    bool Insert(const K &key)
    {
        if (_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }

        Node *cur = _root;
        Node *parent = nullptr;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(key);
        if (key < parent->_key)
            parent->_left = cur;
        else
            parent->_right = cur;

        return true;
    }

    void Inorder()
    {
        _Inorder(_root);
        cout << endl;
    }

    bool Find(const K &key)
    {
        if (_root == nullptr)
            return false;

        Node *cur = _root;
        while (cur)
        {
            if (cur->_key > key)
                cur = cur->_left;
            else if (cur->_key < key)
                cur = cur->_right;
            else
                return true;
        }
        return false;
    }

    bool Erase(const K &key)
    {
        Node *parent = nullptr;
        Node *cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                // 开始删除
                if (cur->_left == nullptr) // 待删除节点没有左孩子
                {
                    if (cur == _root) // 待删除节点为根节点
                    {
                        _root = cur->_right;
                    }
                    else
                    {
                        if (cur == parent->_left) // 删除节点在父节点的左边
                            parent->_left = cur->_right;
                        else // 删除节点在父节点的右边
                            parent->_right = cur->_right;
                    }

                    delete cur;
                }
                else if (cur->_right == nullptr) // 待删除节点没有右孩子
                {
                    if (cur == _root) // 待删除节点为根节点
                    {
                        _root = cur->_left;
                    }
                    else
                    {
                        if (cur == parent->_left) // 删除节点在父节点的左边
                            parent->_left = cur->_left;
                        else // 删除节点在父节点的右边
                            parent->_right = cur->_left;
                    }

                    delete cur;
                }
                else // 待删除节点有左右孩子(替换法删除)
                {
                    // 找到右子树的最小节点进行替换
                    Node *minParent = cur; // minParent不能设置为nullptr
                    Node *min = cur->_right;
                    while (min->_left)
                    {
                        minParent = min;
                        min = min->_left;
                    }

                    swap(cur->_key, min->_key);
                    // 因为替换节点是右子树的最小节点,没有左孩子
                    if (minParent->_left == min) // 替换节点在父节点的左边
                        minParent->_left = min->_right;
                    else
                        minParent->_right = min->_right;

                    delete min;
                }

                return true;
            }
        }
        return false; // 删除失败
    }

    bool FindR(const K &key)
    {
        return _FindR(_root, key);
    }

    bool InsertR(const K& key)
    {
        return _InsertR(_root, key);
    }

    bool EraseR(const K& key)
    {
        return _EraseR(_root, key);
    }

    ~BSTree()
	{
		_Destory(_root);
	}

    BSTree(const BSTree<K>& t)
	{
		_root = _Copy(t._root);
	}

    BSTree<K>& operator=(BSTree<K> t)
    {
        swap(_root, t._root);
        return *this;
    }

private:
    Node* _Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		// 前序遍历拷贝二叉搜索树
		Node* copyRoot = new Node(root->_key);	// 先构造根
		copyRoot->_left = _Copy(root->_left);	// 再构造左子树
		copyRoot->_right = _Copy(root->_right);	// 最后构造右子树

		return copyRoot;
	}

    void _Destory(Node*& root)
	{
		if (root == nullptr)
			return;

		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
		root = nullptr;
	}

    bool _EraseR(Node*& root, const K& key)
    {
        if(root == nullptr) return false;

        if(root->_key < key)
            return _EraseR(root->_right, key);
        else if(root->_key > key)
            return _EraseR(root->_left, key);
        else
        {
            Node* del = root;
            if(root->_left == nullptr)
                root = root->_right;
            else if(root->_right == nullptr)
                root = root->_left;
            else
            {
                Node* min = root->_right;
                while(min->_left)
                {
                    min = min->_left;
                }
                swap(min->_key, root->_key);
                // 交换后子树 root->_right 还是一块二叉搜索树
                return _EraseR(root->_right, key); 
            }

            delete del;
            return true;
        }
    }

    bool _InsertR(Node*& root, const K& key)
    {
        if(root == nullptr)
        {
            root = new Node(key);
            return true;
        }

        if(root->_key < key)
            return _InsertR(root->_right, key);
        else if(root->_key > key)
            return _InsertR(root->_left, key);
        else
            return false; 
    }

    bool _FindR(Node *root, const K &key)
    {
        if (root == nullptr)
            return false;

        if (root->_key < key)
            return _FindR(root->_right, key);
        else if (root->_key > key)
            return _FindR(root->_left, key);
        else
            return true;
    }

    void _Inorder(Node *root)
    {
        if (root == nullptr)
            return;

        _Inorder(root->_left);
        cout << root->_key << " ";
        _Inorder(root->_right);
    }

    Node *_root = nullptr;
};